import java.util.*;
 
/*
public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public static ListNode partition(ListNode node, int x) {
 
        ListNode beforeStart = null;
        ListNode beforeEnd = null;
        ListNode afterStart = null;
        ListNode afterEnd = null;
        ListNode cur = node;
        while(cur!=null) {
            ListNode next = cur.next;
            cur.next = null;
            if(cur.val<x) {
                if(beforeStart == null) {
                    beforeStart = cur;
                    beforeEnd = cur;
                } else {
                    beforeEnd.next = cur;
                    beforeEnd = cur;
                }
            } else {
                if(afterStart == null) {
                    afterStart = cur;
                    afterEnd = cur;
                } else {
                    afterEnd.next = cur;
                    afterEnd = cur;
                }
            }
            cur = next;
        }
        if(beforeEnd!=null) {
            beforeEnd.next = afterStart;
            return beforeStart;
        } else {
            return afterStart;
        }
    }
}